/*
41. First Missing Positive
Total Accepted: 65742 Total Submissions: 274082 Difficulty: Hard

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Subscribe to see which companies asked this question
*/

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        int i = 0;
        int x = nums[0];
        while(i < n){
            if(x < 1 || x > n || nums[x-1] == x){
                i++;
                x = nums[i];
            } else {
                int tmp = nums[x-1];
                nums[x-1] = x;
                x = tmp;
            }
            
        }
        for (i = 0; i < n; i++){
            if (nums[i] != i+1) break;
        }
        return i+1;
    }
};





